import random
class node:
    def __init__(self, data=None,lchild=None,rchild=None):
        self.data=data
        self.lchild=lchild
        self.rchild=rchild


class make_tree:
    def __init__(self):
        self.root=None
        self.queue=[]

    def insert(self,node):
        if self.root is None:
            self.root=node
            self.queue.append(self.root)
        else:
            self.queue.append(node)
            if self.queue[0].lchild is None:
                self.queue[0].lchild=node
            else:
                self.queue[0].rchild=node
                self.queue.pop(0)

    def preorder(self,node):
        if node is None:
            return
        print(node.data,end=' ')
        self.preorder(node.lchild)
        self.preorder(node.rchild)

    def midorder(self, node):
        if node is None:
            return
        self.preorder(node.lchild)
        print(node.data, end=' ')
        self.preorder(node.rchild)
    def finorder(self, node):
        if node is None:
            return
        self.preorder(node.lchild)
        self.preorder(node.rchild)
        print(node.data, end=' ')

    def levelorder(self):
        help_queue=[]
        help_queue.append(self.root)
        while help_queue:
            out_node=help_queue.pop(0)
            print(out_node.data, end=' ')
            if out_node.lchild is not None:
                help_queue.append(out_node.lchild)
            if out_node.rchild is not None:
                help_queue.append(out_node.rchild)

def sorted_exercise():
    dir_dict={'xiaoming':['60kg',18],'bhong':['70kg',36],'ai':['55kg',20]}
    print(sorted(dir_dict.items(),key=lambda x:x[0][1]))
    print(sorted(dir_dict.items(),key=lambda x:x[1][1]))



class people:
    def __init__(self,name,age,height):
        self.name=name
        self.age=age
        self.height=height

    def __repr__(self):
        return f'{self.name},{self.age},{self.height}'


#排序
class Sort:
    def __init__(self,n):
        self.n=n
        self.arr=[]*n
    def random_arr(self):
        for i in range(0,self.n):
            self.arr.append(random.randint(0,100))

    def quick_sort(self,left,right):
        if left<right:
            x=self.once_partition(left,right)
            self.quick_sort(left,x-1)
            self.quick_sort(x+1,right)
        else:
            return

    def once_partition(self,left,right):
        temp=self.arr[right]
        i,k=0,0
        while i<self.n-1:
            if self.arr[i]>=temp:
                i=i+1
            else:
                self.arr[k],self.arr[i]=self.arr[i],self.arr[k]
                k=k+1
                i=i+1
        self.arr[k],self.arr[right]=self.arr[right],self.arr[k]
        return k


if __name__=="__main__":
    tree=make_tree()
    for i in range(0,10):
        Node=node(i)
        tree.insert(Node)
    tree.preorder(tree.root)
    print()
    tree.midorder(tree.root)
    print()
    tree.finorder(tree.root)
    print()
    tree.levelorder()
    print()
    sorted_exercise()
    Peoples=(people('xiaoming',18,170),people('bhong',36,160),people('ai',20,180))
    print(sorted(Peoples,key=lambda Peoples:Peoples.height))
    students=[('xiaoming','60kg',18),('bhong','70kg',36),('ai','40kg',20)]
    print(sorted(students,key=lambda x:(x[1],-x[2])))
    arr1=Sort(10)
    arr1.random_arr()
    print(arr1.arr)
    arr1.quick_sort(0,len(arr1.arr)-1)
    print(arr1.arr)